package com.yuren.codecrushlearn.Q5300;

import java.util.List;
import java.util.Objects;

/**
 * Created with Intellij IDEA.
 * Description:
 *
 * @author 10204
 * @date 2025-05-26 01:40
 */
public class Q5363 {

    /**
     * 贪心算法，先对区间数组进行排序，然后遍历数组，计算出每个区间的等待时间，最后将所有区间的等待时间相加即可。
     * 时间复杂度为 O(nlogn)，空间复杂度为 O(1)。
     * 其中，n 为区间数量。
     * 排序的时间复杂度为 O(nlogn)，遍历数组的时间复杂度为 O(n)，因此总时间复杂度为 O(nlogn)。
     * 空间复杂度为 O(1)，因为只需要常数级别的额外空间。
     *
     * @param intervals
     * @param n
     * @return
     */
    public int findMostIntervals(List<List<Integer>> intervals, int n) {
        intervals.sort((a, b) -> {
            if (Objects.equals(a.get(1), b.get(1))) {
                return a.get(0) - b.get(0);
            } else {
                return a.get(1) - b.get(1);
            }
        });

        int cnt = 1;
        int end = intervals.get(0).get(1);
        // System.out.printf("[%d, %d]\n", intervals.get(0).get(0), intervals.get(0).get(1));
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals.get(i).get(0) >= end) {
                // System.out.printf("[%d, %d]\n", intervals.get(i).get(0), intervals.get(i).get(1));
                cnt++;
                end = intervals.get(i).get(1);
            }
        }
        return cnt;
    }
}
